package 队列;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @description:
 * @author: ChenYunChou
 * @time: 2021/5/1 2021
 */
public class Solution {
    public List<List<Integer>> levelOrder1(TreeNode root){
        //生产FIFO队列
        Queue<TreeNode> Q = new LinkedList<TreeNode>();
        //如果节点不为null,那么加入FIFO队列
        if (root != null){
            Q.offer(root);
        }
        //保存层次遍历结果
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        //利用FIFO进行层次遍历
        while (Q.size() > 0){
            //取出当前里面元素的个数
            final int qSize = Q.size();
            //当前层的结果存放于链表中
            List<Integer> tmp = new LinkedList<Integer>();
            //遍历当前层的每个节点
            for (int i = 0; i < qSize; i++) {
                // 当前层前面的节点先出队
                TreeNode curr = Q.poll();
                // 把结果存放于当前层中
                tmp.add(curr.value);
                //把下一层的节点入队 注意入队时需要非空才能入队
                if (curr.left != null){
                    Q.offer(curr.left);
                }
                if (curr.right != null){
                    Q.offer(curr.right);
                }
            }
            ans.add(tmp);
        }
        return ans;
    }

    public List<List<Integer>> levelOrder2(TreeNode root){
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        //初始化当前层节点
        ArrayList<TreeNode> curLevel = new ArrayList<TreeNode>();
        if (root != null){
            curLevel.add(root);
        }
        while (curLevel.size() > 0){
            //准备用来存放下一层的节点
            ArrayList<TreeNode> nextLevel = new ArrayList<TreeNode>();
            //用来存放当前层的结果
            ArrayList<Integer> curResult = new ArrayList<Integer>();
            //遍历当前层的每个节点
            for (TreeNode cur : curLevel) {
                curResult.add(cur.value);
                if (cur.left != null){
                    nextLevel.add(cur.left);
                }
                if (cur.right != null){
                    nextLevel.add(cur.right);
                }
            }
            curLevel = nextLevel;
            ans.add(curResult);
        }
        return ans;
    }

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            Node last = null;
            for (int i = 1; i <= n; ++i) {
                Node f = queue.poll();
                if (f.left != null) {
                    queue.offer(f.left);
                }
                if (f.right != null) {
                    queue.offer(f.right);
                }
                if (i != 1) {
                    last.next = f;
                }
                last = f;
            }
        }
        return root;
    }

    public int deepestLeavesSum(TreeNode root) {
        int s = 0;
        Queue<TreeNode> cur = new LinkedList<TreeNode>();
        if (root != null){
            cur.offer(root);
        }
        while (cur.size() > 0){
            int size = cur.size();
            int isnull = 0;
            int sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode poll = cur.poll();
                if (poll.left == null && poll.right == null){
                    sum += poll.value;
                    isnull++;
                }
                cur.offer(poll.left);
                cur.offer(poll.right);
            }
            if (isnull == size){
                s = sum;
            }
        }
        return s;
    }
}
